Data communication systems are used to exchange information between devices. The information to be exchanged comprises data that is organized as strings of digital bits formatted so as to be recognizable by other devices and to permit the information to be processed and/or recovered.
The exchange of information may occur over a publically accessible network, such as a communication link between two devices, or over a dedicated network within an organization, or may be between two devices within the same dedicated component, such as within a computer or point of sale device.
The devices may be relatively large computer systems, telecommunication devices, cellular phones, monitoring devices, sensors, electronic wallets and smart cards, and a wide variety of devices that are connected to transfer data between two or more of such devices. A large number of communication protocols have been developed to allow the exchange of data between different devices. The communication protocols permit the exchange of data in a robust manner, often with error correction and error detection functionality, and for the data to be directed to the intended recipient and recovered for further use.
Because the data may be accessible to other devices, it is vulnerable to interception and/or manipulation. The sensitive nature of the information requires that steps are taken to secure the information and ensure its integrity.
A number of techniques, collectively referred to as encryption protocols, have been developed to provide the required attributes and ensure security and/or integrity in the exchange of information. These techniques utilize a key that is combined with the data.
There are two main types of cryptosystems that implement the protocols, symmetric key cryptosystems and asymmetric or public key cryptosystems. In a symmetric key cryptosystem, the devices exchanging information share a common key that is known only to the devices intended to share the information. Symmetric key systems have the advantage that they are relatively fast and therefore able to process large quantities of data in a relatively short time, even with limited computing power. However, the keys must be distributed in a secure manner to the different devices, which leads to increased overhead and vulnerability if the key is compromised.
A symmetric or public key cryptosystems utilize a key pair, one of which is public and the other private, associated with each device. The public key and private key are related by a “hard” mathematical problem so that even if the public key and the underlying problem are known, the private key cannot be recovered in a feasible time. One such problem is the factoring of the product of two large primes, as utilized in RSA cryptosystems. Another is the discrete log problem in a finite cyclic group. A generator, α, of the underlying group is identified as a system parameter and a random integer, k, generated for use as a private key. To obtain a public key, K, a k-fold group operation is performed so that K=f(α,k).
Different groups may be used in discrete log cryptosystems including the multiplicative group of integers modulus a prime, usually denoted Zp* and consisting of the integers to p−1. The group operation is multiplication so that K=f(αk).
Another group that is used for enhanced security is an elliptic curve group. The elliptic curve group consists of pairs of elements, one of which is designated x and the other y, in a group of order n that satisfy the relationship y2 mod p=x3+ax+b mod p. Each such pair of elements is a point on the curve, and a generator of the group is designated as a point P. The group operation is addition, so a private key k will have a corresponding public key f(kP), which is itself a point resulting from a k-fold group operation on the base point P and represented as a pair of bit strings, each of which is an element of the underlying field.
Public key cryptosystems reduce the infrastructure necessary with symmetric key cryptosystems. A device may generate an integer k, and generate the corresponding public key kP. The public key is published so it is available to other devices. The device may then use a suitable signature protocol to sign a message using the private key k and other devices can confirm the integrity of the message using the public key kP.
Similarly, a device may encrypt a message to be sent to another device using the other device's public key, which can then be recovered by the other device using the private key. However, these protocols are computationally intensive, and therefore relatively slow, compared with symmetric cryptosystem protocols.
Public key cryptosystems may also be used to establish a key that is shared between two devices. In its simplest form, as proposed by Diffie-Hellman, each device sends a public key to the other device. Both devices then combine the received public key with their private key to obtain a shared key.
One device, usually referred to as an entity, Alice, generates a private key ka and sends another device, or entity, Bob, the public key kaP.
Bob generates a private key kb and sends Alice the public key kbP
Alice computes ka.kbP and Bob computes kb.kaP so they share a common key K=ka.kbP=kb.kaP. The shared key may then be used in a symmetric key protocol. Neither Alice nor Bob may recover the private key of the other, and third parties cannot reconstruct the shared key.
The protocols that have been developed require the use of a public key of another party. In order to validate the public key as that of the intended entity, a trusted hierarchy has been established in which a trusted entity, referred to as the Certification Authority or CA, validates the public key of entities within its domain. Each entity will have the public key of the CA embedded and uses that public key to validate the public key of the individual entities.
The usual form of validation requires the CA to generate a certificate that is the CA's signature of a message that includes the public key of the entity. An entity that wishes to use another entity's public key can then verify the certificate using the CA's public key and extract from the message the public key of the other entity. Such a protocol can however be computationally and bandwidth intensive.
An alternative protocol uses implicitly certified public keys in which the public key of an entity is reconstructed by the user, rather than transported as a public key certificate. One widely accepted key agreement scheme utilizing implicit certificates is described in U.S. Pat. No. 6,792,530. In its simplest form, an implicitly certified public key of an entity A is provided from a unique identity, IDA, and public key reconstruction data, γA, that is generated by a trusted authority and associated with the entity A. The pair IDA,γA are the implicit certificate of the public key of A and can be used with published public information to reconstruct the ephemeral public key. Thus, in the first example provided in U.S. Pat. No. 6,792,530, the trusted authority CA chooses a random number c, and computes a corresponding public value β, where β=αc mod p and α is a generator of the finite field. CA chooses a second random number ca and computes γA as αca mod p. A value f is computed as a function F(IA,γA) and a private key “a” derived from the relationship 1=cf+caa (mod n). The values γA, IA and a are then sent to the entity A. This requires a secure channel as the private key is being transferred. The selection of the random numbers is also entirely the responsibility of the CA, who will also have knowledge of the private key a.
In subsequent embodiments described in U.S. Pat. No. 6,792,530, the entity A participates in the selection of the random numbers and a secure channel is avoided through the use of a shared key to encrypt a component used to generate the private key of the entity A. However, the identity IDA and public key reconstruction data γA are sent in the clear, leaving them vulnerable to inadvertent and/or malicious modification.
It is therefore an object of the present invention to provide an implicitly certified public key scheme in which the above disadvantages are obviated or mitigated.